// 版权所有2009 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 二进制到十进制浮点转换。
// 算法：
// 1）以多精度小数存储尾数
// 2）按指数移位十进制
// 3）读取数字并格式化

package strconv

import "math"

// TODO:移到别处？
type floatInfo struct {
	mantbits uint
	expbits  uint
	bias     int
}

var float32info = floatInfo{23, 8, -127}
var float64info = floatInfo{52, 11, -1023}

// FormatFloat将浮点数f转换为字符串，
// 根据格式fmt和精度prec。它舍入
// 结果，假设原始值是从位大小位的浮点
// 值获得的（32表示float32，64表示float64）。格式fmt是其中之一：格式fmt是
// /'b'（-ddddp±ddd，一个二进制指数），
// /'e'（-d.DDDDD±dd，一个十进制指数），
// /'e'（-d.DDDDD±dd，一个十进制指数），
// /'G'（'E'表示大指数，f'表示其他），
// /'x'（-0xd.DDP±ddd，十六进制分数和二进制指数），或
// /'x'（-0xd.DDP±ddd，十六进制分数和二进制指数）。
// 
// 精度prec控制数字（不包括指数）
// 以“e”、“e”、“f”、“g”、“g”、“x”和“x”格式打印。
// 对于“e”、“e”、“f”、“x”和“x”，它是小数点后的位数。
// 对于“g”和“g”，它是有效位数的最大值（后面的
// 零被删除）。
// 特殊精度-1使用最小位数
// 必要时，ParseFloat将精确返回f。
func FormatFloat(f float64, fmt byte, prec, bitSize int) string {
	return string(genericFtoa(make([]byte, 0, max(prec+4, 24)), f, fmt, prec, bitSize))
}

// AppendFloat将由FormatFloat生成的浮点数f、
// 的字符串形式追加到dst，并返回扩展缓冲区。
func AppendFloat(dst []byte, f float64, fmt byte, prec, bitSize int) []byte {
	return genericFtoa(dst, f, fmt, prec, bitSize)
}

func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte {
	var bits uint64
	var flt *floatInfo
	switch bitSize {
	case 32:
		bits = uint64(math.Float32bits(float32(val)))
		flt = &float32info
	case 64:
		bits = math.Float64bits(val)
		flt = &float64info
	default:
		panic("strconv: illegal AppendFloat/FormatFloat bitSize")
	}

	neg := bits>>(flt.expbits+flt.mantbits) != 0
	exp := int(bits>>flt.mantbits) & (1<<flt.expbits - 1)
	mant := bits & (uint64(1)<<flt.mantbits - 1)

	switch exp {
	case 1<<flt.expbits - 1:
		// Inf，NaN 
		var s string
		switch {
		case mant != 0:
			s = "NaN"
		case neg:
			s = "-Inf"
		default:
			s = "+Inf"
		}
		return append(dst, s...)

	case 0:
		// 非规范化
		exp++

	default:
		// 添加隐式顶位
		mant |= uint64(1) << flt.mantbits
	}
	exp += flt.bias

	// 选择简单的二进制、十六进制格式。
	if fmt == 'b' {
		return fmtB(dst, neg, mant, exp, flt)
	}
	if fmt == 'x' || fmt == 'X' {
		return fmtX(dst, prec, fmt, neg, mant, exp, flt)
	}

	if !optimize {
		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
	}

	var digs decimalSlice
	ok := false
	// 负精度意味着“只需要精确到所需的程度”。
	shortest := prec < 0
	if shortest {
		// 使用Ryu算法。
		var buf [32]byte
		digs.d = buf[:]
		ryuFtoaShortest(&digs, mant, exp-int(flt.mantbits), flt)
		ok = true
		// 最短表示模式的精度。
		switch fmt {
		case 'e', 'E':
			prec = max(digs.nd-1, 0)
		case 'f':
			prec = max(digs.nd-digs.dp, 0)
		case 'g', 'G':
			prec = digs.nd
		}
	} else if fmt != 'f' {
		// 固定位数。
		digits := prec
		switch fmt {
		case 'e', 'E':
			digits++
		case 'g', 'G':
			if prec == 0 {
				prec = 1
			}
			digits = prec
		}
		var buf [24]byte
		if bitSize == 32 && digits <= 9 {
			digs.d = buf[:]
			ryuFtoaFixed32(&digs, uint32(mant), exp-int(flt.mantbits), digits)
			ok = true
		} else if digits <= 18 {
			digs.d = buf[:]
			ryuFtoaFixed64(&digs, mant, exp-int(flt.mantbits), digits)
			ok = true
		}
	}
	if !ok {
		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
	}
	return formatDigits(dst, shortest, neg, digs, prec, fmt)
}

// bigFtoa使用多精度计算格式化浮点。
func bigFtoa(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
	d := new(decimal)
	d.Assign(mant)
	d.Shift(exp - int(flt.mantbits))
	var digs decimalSlice
	shortest := prec < 0
	if shortest {
		roundShortest(d, mant, exp, flt)
		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
		// 最短表示模式的精度。
		switch fmt {
		case 'e', 'E':
			prec = digs.nd - 1
		case 'f':
			prec = max(digs.nd-digs.dp, 0)
		case 'g', 'G':
			prec = digs.nd
		}
	} else {
		// 适当地四舍五入。
		switch fmt {
		case 'e', 'E':
			d.Round(prec + 1)
		case 'f':
			d.Round(d.dp + prec)
		case 'g', 'G':
			if prec == 0 {
				prec = 1
			}
			d.Round(prec)
		}
		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
	}
	return formatDigits(dst, shortest, neg, digs, prec, fmt)
}

func formatDigits(dst []byte, shortest bool, neg bool, digs decimalSlice, prec int, fmt byte) []byte {
	switch fmt {
	case 'e', 'E':
		return fmtE(dst, neg, digs, prec, fmt)
	case 'f':
		return fmtF(dst, neg, digs, prec)
	case 'g', 'G':
		// 将修剪“e”形式的尾随分数零。如果转换得出的指数小于-4或大于或等于精度，则使用
		eprec := prec
		if eprec > digs.nd && digs.nd >= digs.dp {
			eprec = digs.nd
		}
		// /%e。
		// 如果精度是最短的，则使用精度6进行此决定。
		if shortest {
			eprec = 6
		}
		exp := digs.dp - 1
		if exp < -4 || exp >= eprec {
			if prec > digs.nd {
				prec = digs.nd
			}
			return fmtE(dst, neg, digs, prec-1, fmt+'e'-'g')
		}
		if prec > digs.dp {
			prec = digs.nd
		}
		return fmtF(dst, neg, digs, max(prec-digs.dp, 0))
	}

	// 未知格式
	return append(dst, '%', fmt)
}

// 将最短的d（=mant*2^exp）舍入到最短的位数
// 这样可以精确地重构原始浮点值。
func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
	// 如果尾数为零，则数字为零；现在停下来。
	if mant == 0 {
		d.nd = 0
		return
	}

	// 计算上限和下限，使上限和下限（可能包括在内）之间的任何十进制数
	// 将四舍五入为原始浮点数。

	// 我们马上就会发现这个数字已经是最短的了。假设d不是非规范的，因此2^exp<=d<10^dp。
	// 最接近的较短数字至少距离10^（dp nd）。
	// 下面计算的下限/上限位于距离
	// 最多2^（exp-mantbits）。
	// 
	// 因此，如果10^（dp-nd）>2^（exp-mantbits），
	// 或等效log2（10）*（dp-nd）>exp-mantbits，则该数字已经最短。
	// 如果332/100*（dp-nd）>=exp-mantbits（log2（10）>3.32），则为真。
	minexp := flt.bias + 1 // 最小可能指数
	if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) {
		// 该数字已最短。
		return
	}

	// d=mant<<（exp-mantbits）
	// 下一个最高浮点数是mant+1<<exp mantbits。
	// 我们的上限介于，mant*2+1<<exp-mantbits-1之间。
	upper := new(decimal)
	upper.Assign(mant*2 + 1)
	upper.Shift(exp - int(flt.mantbits) - 1)

	// d=mant<<（exp-mantbits）
	// 下一个最低浮点数是mant-1<<exp-mantbits，
	// 除非mant-1删除有效位且exp不是最小exp，否则下一个最低浮点数是mant*2-1<<exp-mantbits-1。
	// 无论哪种方式，都可以称之为mantlo。
	// 我们的下限介于，mantlo*2+1之间。
	var mantlo uint64
	var explo int
	if mant > 1<<flt.mantbits || exp == minexp {
		mantlo = mant - 1
		explo = exp
	} else {
		mantlo = mant*2 - 1
		explo = exp - 1
	}
	lower := new(decimal)
	lower.Assign(mantlo*2 + 1)
	lower.Shift(explo - int(flt.mantbits) - 1)

	// 只有当
	// 原始尾数为偶数时，上下界才是可能的输出，因此IEEE舍入偶数
	// 将舍入原始尾数，而不是相邻尾数。
	inclusive := mant%2 == 0

	// 当我们走到数字时，我们想知道四舍五入是否会落在上限之内。这由upperdelta跟踪：
	// 
	// 如果upperdelta==0，则d和upper的数字到目前为止是相同的。
	// 
	// 如果upperdelta==1，我们在
	// 上一个数字上看到d和upper之间的差值为1，随后d的差值为9，upper的差值为0。
	// （因此，如果是排他性的，则舍入可能不在限制范围内。）
	// 
	// 如果upperdelta==2，则差值大于1 
	// 我们知道舍入在限制范围内。
	var upperdelta uint8

	// 现在我们可以计算出所需的最小位数。
	// 一直往前走，直到d将自己与上下区分开来。
	for ui := 0; ; ui++ {
		// 下限、d和上限的小数点可能位于不同的
		// 位。在本例中，上限是最长的，因此我们从
		// ui==0开始迭代，并在（可能的）1处开始li和mi。
		mi := ui - upper.dp + d.dp
		if mi >= d.nd {
			break
		}
		li := ui - upper.dp + lower.dp
		l := byte('0') // 低位
		if li >= 0 && li < lower.nd {
			l = lower.d[li]
		}
		m := byte('0') // 中间位
		if mi >= 0 {
			m = d.d[mi]
		}
		u := byte('0') // 高位
		if ui < upper.nd {
			u = upper.d[ui]
		}

		// 如果lower有不同的数字
		// 或者lower包含在内，并且恰好是
		// 向下四舍五入的结果（即，我们已经到达了lower的最后一位），则可以向下四舍五入（截断）. 
		okdown := l != m || inclusive && li+1 == lower.nd

		switch {
		case upperdelta == 0 && m+1 < u:
			// 示例：
			// m=12345xxx 
			// u=12347xxx 
			upperdelta = 2
		case upperdelta == 0 && m != u:
			// 示例：
			// m=12345xxx 
			// u=12346xxx 
			upperdelta = 1
		case upperdelta == 1 && (m != '9' || u != '0'):
			// 示例：
			// m=1234598x 
			// u=1234600x 
			upperdelta = 2
		}
		// upper有一个不同的数字，或者upper 
		// 包含在内，或者upper大于四舍五入的结果。
		okup := upperdelta > 0 && (inclusive || upperdelta > 1 || ui+1 < upper.nd)

		// 如果两种方法都可以的话，就转到最近的一种。
		// 如果可以只做一个，那么就去做。
		switch {
		case okdown && okup:
			d.Round(mi + 1)
			return
		case okdown:
			d.RoundDown(mi + 1)
			return
		case okup:
			d.RoundUp(mi + 1)
			return
		}
	}
}

type decimalSlice struct {
	d      []byte
	nd, dp int
	neg    bool
}

// /%e:-d.ddddd e±dd 
func fmtE(dst []byte, neg bool, d decimalSlice, prec int, fmt byte) []byte {
	// 符号
	if neg {
		dst = append(dst, '-')
	}

	// 第一位
	ch := byte('0')
	if d.nd != 0 {
		ch = d.d[0]
	}
	dst = append(dst, ch)

	// /.更多数字
	if prec > 0 {
		dst = append(dst, '.')
		i := 1
		m := min(d.nd, prec+1)
		if i < m {
			dst = append(dst, d.d[i:m]...)
			i = m
		}
		for ; i <= prec; i++ {
			dst = append(dst, '0')
		}
	}

	// e±
	dst = append(dst, fmt)
	exp := d.dp - 1
	if d.nd == 0 { // 特例：0的指数为0 
		exp = 0
	}
	if exp < 0 {
		ch = '-'
		exp = -exp
	} else {
		ch = '+'
	}
	dst = append(dst, ch)

	// dd或ddd 
	switch {
	case exp < 10:
		dst = append(dst, '0', byte(exp)+'0')
	case exp < 100:
		dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
	default:
		dst = append(dst, byte(exp/100)+'0', byte(exp/10)%10+'0', byte(exp%10)+'0')
	}

	return dst
}

func fmtF(dst []byte, neg bool, d decimalSlice, prec int) []byte {
	if neg {
		dst = append(dst, '-')
	}

	if d.dp > 0 {
		m := min(d.nd, d.dp)
		dst = append(dst, d.d[:m]...)
		for ; m < d.dp; m++ {
			dst = append(dst, '0')
		}
	} else {
		dst = append(dst, '0')
	}

	// 分数
	if prec > 0 {
		dst = append(dst, '.')
		for i := 0; i < prec; i++ {
			ch := byte('0')
			if j := d.dp + i; 0 <= j && j < d.nd {
				ch = d.d[j]
			}
			dst = append(dst, ch)
		}
	}

	return dst
}

// /%b:-ddddddp±ddd 
func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
	// 符号
	if neg {
		dst = append(dst, '-')
	}

	// 尾数
	dst, _ = formatBits(dst, mant, 10, false, true)

	// /p 
	dst = append(dst, 'p')

	// /±指数
	exp -= int(flt.mantbits)
	if exp >= 0 {
		dst = append(dst, '+')
	}
	dst, _ = formatBits(dst, uint64(exp), 10, exp < 0, true)

	return dst
}

// /%x:-0x1.yyyyyy p±ddd或-0x0p+0。（y为十六进制数字，d为十进制数字）
func fmtX(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
	if mant == 0 {
		exp = 0
	}

	// 移位数字，使前导1（如果有）位于第1位<<60。
	mant <<= 60 - flt.mantbits
	for mant != 0 && mant&(1<<60) == 0 {
		mant <<= 1
		exp--
	}

	// 如有要求，则为四舍五入。
	if prec >= 0 && prec < 15 {
		shift := uint(prec * 4)
		extra := (mant << shift) & (1<<60 - 1)
		mant >>= 60 - shift
		if extra|(mant&1) > 1<<59 {
			mant++
		}
		mant <<= 60 - shift
		if mant&(1<<61) != 0 {
			// 缠绕。
			mant >>= 1
			exp++
		}
	}

	hex := lowerhex
	if fmt == 'X' {
		hex = upperhex
	}

	// 符号，0x，前导数字
	if neg {
		dst = append(dst, '-')
	}
	dst = append(dst, '0', fmt, '0'+byte((mant>>60)&1))

	// 。分数
	mant <<= 4 // 删除前导0或1 
	if prec < 0 && mant != 0 {
		dst = append(dst, '.')
		for mant != 0 {
			dst = append(dst, hex[(mant>>60)&15])
			mant <<= 4
		}
	} else if prec > 0 {
		dst = append(dst, '.')
		for i := 0; i < prec; i++ {
			dst = append(dst, hex[(mant>>60)&15])
			mant <<= 4
		}
	}

	// p±
	ch := byte('P')
	if fmt == lower(fmt) {
		ch = 'p'
	}
	dst = append(dst, ch)
	if exp < 0 {
		ch = '-'
		exp = -exp
	} else {
		ch = '+'
	}
	dst = append(dst, ch)

	// /dd或ddd或dddd 
	switch {
	case exp < 100:
		dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
	case exp < 1000:
		dst = append(dst, byte(exp/100)+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')
	default:
		dst = append(dst, byte(exp/1000)+'0', byte(exp/100)%10+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')
	}

	return dst
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
